<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from comptrees.tnf on 19 December 2010 -->

<TITLE>LIDO -- Computations in Trees - Symbol Computations</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM>
<A HREF="http://eli-project.sourceforge.net/">
<IMG SRC="gifs/elilogo.gif" BORDER=0>
</A>&nbsp;
</TD>
<TD WIDTH="25" VALIGN=BOTTOM>
<img src="gifs/empty.gif" WIDTH=25 HEIGHT=25>
</TD>
<TD ALIGN=LEFT WIDTH="475" VALIGN=BOTTOM>
<A HREF="index.html"><IMG SRC="gifs/title.png" BORDER=0></A>
</TD>
<!-- |DELETE FOR SOURCEFORGE LOGO|
<TD>
<a href="http://sourceforge.net/projects/eli-project">
<img
  src="http://sflogo.sourceforge.net/sflogo.php?group_id=70447&amp;type=13"
  width="120" height="30"
  alt="Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads"/>
</a>
</TD>
|DELETE FOR SOURCEFORGE LOGO| -->
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_1.html#SEC1">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<A HREF="mailto:eli-project-users@lists.sourceforge.net">
<IMG SRC="gifs/button_mail.gif" BORDER=0 ALIGN="left"></A>
<A HREF="index.html"><IMG SRC="gifs/home.gif" BORDER=0 ALIGN="right"></A>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>LIDO -- Computations in Trees</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_3.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_5.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<H1><A NAME="SEC9" HREF="comptrees_toc.html#SEC9">Symbol Computations</A></H1>
<A NAME="IDX53"></A>
<P>
In this section we introduce constructs that associate computations to
tree grammar symbols rather than to rule contexts. They can be used for
computations which are conceptually connected with symbols, i. e. they
have to be executed once for each such symbol node and they are not
distinguished for the contexts in which the symbol occurs.
<P>
The use of symbol computations makes specifications even more
independent of the particular tree grammar, and hence reduces the chance
to be invalidated by grammar changes. Well designed symbol computations
may be reused at different places in one specification, and even in
specifications of different language processors.
<P>
In the following we demonstrate the use of symbol computations, and
introduce a construct for their reuse.
<P>
<H2><A NAME="SEC10" HREF="comptrees_toc.html#SEC10">Basic Symbol Computations</A></H2>
<P>
Consider the expression grammar given in the example of  <A HREF="comptrees_2.html#SEC3">Value Dependencies</A>.
For the purpose of this
example assume that we want to trace the computation of expression
values, and print
<CODE>Expr.value</CODE> for each <CODE>Expr</CODE> node. We could associate that
computation to both lower <CODE>Expr</CODE> context.
But this computation does not refer to those
particular contexts, it only depends on one <CODE>Expr</CODE> attribute. Hence
we better associate it to the <CODE>Expr</CODE> symbol:
<P>
<PRE>
   SYMBOL Expr COMPUTE
      printf ("expression value %d in line %d\n", THIS.value, LINE);
   END;
</PRE>
<A NAME="IDX54"></A>
<A NAME="IDX55"></A>
<P>
Symbol computations may use attributes of the symbol by the notation
<CODE>THIS.AttributeName</CODE>.
<P>
The next example in Figure 12 shows how attributes are computed by
symbol computations. It rewrites the usage count example of Figure 8.
Both of its computations are in fact independent of the
particular rule context.
<P>
<PRE>
   ATTR Count: int;

   SYMBOL Usage COMPUTE
     SYNT.Count = 1;
   END;

   SYMBOL Block COMPUTE
      printf ("%d uses occurred\n",
              CONSTITUENTS Usage.Count SHIELD Block
              WITH (int, ADD, IDENTICAL, ZERO));
   END;
</PRE>
Figure 12: Symbol Computations for Usage Count
<A NAME="IDX56"></A>
<A NAME="IDX57"></A>
<P>
An attribute that is defined by a symbol computation has to be
classified <CODE>SYNT</CODE> or <CODE>INH</CODE>, like <CODE>SYNT.Count</CODE> above (instead
of <CODE>THIS.Count</CODE> if the attribute were used in the computation). It
determines whether the computation is intended for the lower <CODE>SYNT</CODE>
or the upper <CODE>INH</CODE> contexts of the symbol.
<A NAME="IDX58"></A>
<A NAME="IDX59"></A>
<A NAME="IDX60"></A>
<P>
The symbol computation of <CODE>Block</CODE> above shows that
<CODE>CONSTITUENTS</CODE> constructs may be used in symbol computations as
well as in rule contexts. The same applies to <CODE>INCLUDING</CODE> and
<CODE>CHAIN</CODE> as shown below.
<P>
The above example reduces the amount of key strokes only slightly
compared with that of Figure 8. But it makes this part of the
specification invariant to modifications of the contexts where
<CODE>Usage</CODE> and <CODE>Block</CODE> occur. The productions for <CODE>Block</CODE>
and for <CODE>Usage</CODE> may be modified without affecting these symbol
computations.
<P>
Now consider the computation of nesting depth of blocks in Figure 6. The
computation of <CODE>Block.depth</CODE> can also be
specified as a symbol computation:
<P>
<PRE>
   SYMBOL Block COMPUTE
     INH.depth = ADD (INCLUDING Block.depth, 1);
   END;
</PRE>
<P>
In this case the computation is intended to go to the upper contexts of <CODE>Block</CODE>, indicated by <CODE>INH.depth</CODE>. That is correct for any context where <CODE>Block</CODE> is a descendant of a <CODE>Statement</CODE>. But in the <CODE>Program</CODE> context
the <CODE>depth</CODE> of the root <CODE>Block</CODE> must be computed to 0, rather than by
the above symbol computation. So we keep the computation of Figure 6:
<P>
<PRE>
   RULE: Root ::= Block COMPUTE
     Block.depth = 0;
   END;
</PRE>
<P>
It overrides the above symbol computation: A rule computation overrides
a symbol computation for the same attribute.
<P>
The example demonstrates a design rule:
<BLOCKQUOTE>
   General context independent computations are specified by symbol
   computations.  They may be overridden in special cases by computations
   in rule contexts.
</BLOCKQUOTE>
<A NAME="IDX61"></A>
<P>
The technique of overriding can also be used to specify default computations:
A symbol computation specifies an attribute value for most occurrences
of the symbol. In some contexts it is overridden by rule specific
computations.
<P>
Finally we demonstrate how <CODE>CHAINS</CODE> are used in symbol
computations.  In Figure 11 addresses are computed for variable
definitions. It is rewritten, as shown in Figure 13. In the second
computation <CODE>THIS.RelAdr</CODE> occurs twice with different manings: it
refers to the incoming <CODE>CHAIN</CODE> value in the call of <CODE>ADD</CODE>,
whereas the outgoing <CODE>CHAIN</CODE> value is defined on the
lefthand-side of the computation. <CODE>CHAIN</CODE> accesses are distinguished
by their use or definition, rather than by <CODE>SYNT</CODE> and <CODE>INH</CODE> as
in case of attributes.
<P>
<PRE>
   CHAIN RelAdr: int;

   SYMBOL Block COMPUTE
     CHAINSTART HEAD.RelAdr = 0;
   END;

   SYMBOL Definition COMPUTE
     THIS.RelAdr = ADD (THIS.RelAdr, VariableSize);
   END;
</PRE>
Figure 13: Symbol Computations for Addresses of Variables
<P>
<H2><A NAME="SEC11" HREF="comptrees_toc.html#SEC11">Reuse of Symbol Computations</A></H2>
<A NAME="IDX62"></A>
<A NAME="IDX63"></A>
<P>
Symbol computations are a well suited base for reuse of specifications:
A computational concept is specified by a set of symbol computations.
Then it is applied by inheriting it to grammar symbols. (Here the term
inheritance is used in the sense of object oriented programming; it must
not be confused with the class of inherited attributes.)
<A NAME="IDX64"></A>
<P>
Assume we want to enumerate occurrences of non-recursive language
constructs, e. g. definitions in a block and variable uses in each
single statement. We first describe this computational concept by
computations associated to new <CODE>CLASS</CODE> symbols that do not occur in the
tree grammar. In Figure 14 use a <CODE>CHAIN</CODE> as in the examples of
 <A HREF="comptrees_3.html#SEC8">Left-to-Right Dependencies</A>.
<P>
<PRE>
   CHAIN Occurrence: int;
   ATTR OccNo, TotalOccs: int;

   CLASS SYMBOL OccRoot COMPUTE
     CHAINSTART HEAD.Occurrence = 0;
     THIS.TotalOccs = TAIL.Occurrence;
   END;

   CLASS SYMBOL OccElem COMPUTE
     SYNT.OccNo = THIS.Occurrence;
     THIS.Occurrence = ADD (SYNT.OccNo, 1);
   END;
</PRE>
Figure 14: Computationel Concept Occurrence Count
<P>
The above computations correspond to those for computing addresses in
Figure 11. They are extended by computations of attributes
<CODE>TotalOccs</CODE> (for the total number of enumerated constructs) and
<CODE>OccNo</CODE> (for the current number of the enumerated element). Further
computations may use these attributes, instead of referring to the
<CODE>CHAIN</CODE>, which can be considered as an implementation mechanism of the
enumeration computation.
<P>
The <CODE>CLASS</CODE> symbols <CODE>OccRoot</CODE> and <CODE>OccElem</CODE> represent two roles
of this computational concept: The root of a subtree where elements are
counted, and the elements to be counted. They are distinguished from
symbols of the tree grammar by specifying them <CODE>CLASS</CODE> <CODE>SYMBOL</CODE>.
<P>
We now apply this count specification to symbols of our tree grammar:
<P>
<PRE>
   SYMBOL Block INHERITS OccRoot END;
   SYMBOL Definition INHERITS OccElem END;
</PRE>
<P>
<CODE>Block</CODE> inherits the role <CODE>OccRoot</CODE> and <CODE>Definition</CODE>
inherits the role <CODE>OccElem</CODE>. Those constructs yield the same effect
as if the computations for <CODE>OccRoot</CODE> (<CODE>OccElem</CODE>) were
associated to <CODE>Block</CODE> (<CODE>Definition</CODE>).
As a consequence further computations may use the attributes
<CODE>Definition.OccNo</CODE> (the number of a definition in a block), and
<CODE>Block.TotalOccs</CODE> (the total number of definitions in that block).
<P>
The second enumeration application is specified in the same way:
<P>
<PRE>
   SYMBOL Statement INHERITS OccRoot END;
   SYMBOL Usage INHERITS OccElem END;
</PRE>
<P>
Of course we have to make sure that different applications do not
interact.  For example a third application enumerating the variable
assignments would collide with the definition enumeration. This
computational concept is not applicable to the enumeration of blocks
which are recursive constructs. The specification module library of Eli
provides more general applicable modules, and a mechanism that avoids
such collisions. The application of those library modules is based on
the technique of inheritance of computational roles as described here.
<P>
We finally show how several computational concepts may be combined:
Assume that we want to print the total number of enumerated constructs.
We again introduce a <CODE>CLASS</CODE> symbol for this computation:
<P>
<PRE>
   CLASS SYMBOL PrintTotalOccs COMPUTE
      printf ("construct in line %d has %d elements\n",
              LINE, THIS.TotalOccs);
   END;
</PRE>
<P>
This computation is applied by adding
<P>
<PRE>
   SYMBOL Block INHERITS PrintTotalOccs END;
</PRE>
<P>
to the specification and correspondingly for <CODE>Definition</CODE>. The two
<CODE>INHERITS</CODE> constructs can also be combined to one:
<P>
<PRE>
   SYMBOL Block INHERITS OccRoot, PrintTotalOccs END;
</PRE>
<P>
We alternatively could extend the role of the enumeration root
<CODE>OccRoot</CODE> such that the total number is always printed by
<P>
<PRE>
   CLASS SYMBOL OccRoot INHERITS PrintTotalOccs END;
</PRE>
<P>
In this case each symbol that inherits the computation of <CODE>OccRoot</CODE>
also inherits the computation of <CODE>PrintTotalOccs</CODE>.
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_3.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_5.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="comptrees_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>
